package Hot100.Medium.BinarySearch;

public class LC287 {
    public static void main(String[] args) {

    }

    public int findDuplicate(int[] nums){
        int min = 1; // 思想是二分法的思想，而不是严格的二分法，这里的min是从1开始的数字，不要理解为开闭区间
        int max = nums.length - 1;
        int ans = -1;
        while(min <= max){
            int mid = min + (max - min) / 2;
            int count = 0;
            for(int num : nums){// 统计 <= mid的个数，比如[1, 2, 2, 3, 4],mid=2,[1,2,2]这些数比mid小，但是有三个数字，证明重复的就在里面
                if(num <= mid){
                    count++;
                }
            }
            if(count > mid){ // 证明有重复数，就在[left,mid]上
                ans = mid;
                max = mid - 1;
            } else { // // 重复数在 [mid+1, right]
                min = mid + 1;
            }
        }
        return ans;
    }
}
